import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/13 14:28
 * @description 树形背包问题，由于附件不超过2，那么可以从这下文章，进行分组，利用分组背包解决问题
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 总钱数 N, 可购买物品的个数 m
            int N = sc.nextInt(), m = sc.nextInt();
            sc.nextLine();
            // 获取输入
            Map<Integer, Good> goodMap = new HashMap<>();
            for (int i = 2; i < m + 2; i++) {
                // 单件物品的价格 v, 重要度 p, 主件还是附件 q
                int v =  sc.nextInt(), p = sc.nextInt(), q  = sc.nextInt();
                goodMap.put(i - 1, new Good(i - 1, v, p , q));
            }
            // 预处理主件和附件的关系
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (Good good : goodMap.values()) {
                if (good.q == 0) {
                    // 属于主件
                    if (!map.containsKey(good.idx)) {
                        map.put(good.idx, new ArrayList<>());
                    }
                }else {
                    // 属于附件, 将该附件添加到主件的list中
                    List<Integer> list = map.getOrDefault(good.q, new ArrayList<>());
                    list.add(good.idx);
                    map.put(good.q, list);
                }
            }

            // 构建物品组，形成分组背包
            List<List<int[]>> lists = new ArrayList<>();
            for (int root : map.keySet()) {
                // 每一个root对应 一个主件
                List<int[]> group = new ArrayList<>();
                Good good = goodMap.get(root);
                int rootValue = good.value, rootWeight = good.value * good.p;
                // 不添加附件, 这一组的价格和重要度为
                group.add(new int[] {rootValue, rootWeight});

                List<Integer> sub = map.get(root);
                // 选择附件
                for (int i = 0; i < sub.size(); i++) {
                    int x = sub.get(i);
                    Good goodx = goodMap.get(x);
                    // 选一件附件
                    int xV = goodx.value, xW = goodx.value * goodx.p;
                    group.add(new int[] {rootValue + xV, rootWeight + xW});
                    for (int j = i + 1; j < sub.size(); j++) {
                        int y = sub.get(j);
                        Good goody = goodMap.get(y);
                        // 选两件附件
                        group.add(new int[] {rootValue + xV + goody.value, rootWeight + xW + goody.value * goody.p});
                    }
                }
                lists.add(group);
            }

            // 分组背包一维空间优化：定义 f[i][j] 为考虑前 i 件物品，使用容量不超过 j 的最大价值
            int[] f = new int[N + 1];
            // 枚举物品组
            for (int i = 0; i < lists.size(); i++) {
                List<int[]> group = lists.get(i);
                // 枚举背包容量
                for (int j = N; j >= 0; j--) {
                    // 枚举决策（选哪个组内物品）
                    for (int k = 0; k < group.size(); k++) {
                        int[] info = group.get(k);
                        int vi = info[0], wi = info[1];
                        if (j >= vi) {
                            f[j] = Math.max(f[j], f[j - vi] + wi);
                        }
                    }
                }
            }

            System.out.println(f[N]);
        }
    }
}
class Good {
    int idx;
    int value;
    int p;
    int q;
    public Good(int idx, int value, int p, int q) {
        this.idx = idx;
        this.value = value;
        this.p = p;
        this.q = q;
    }
}
